package club.xiaojiawei.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Objects;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 4/28/22 8:36 PM
 * @question 350.两个数组的交集II
 * @description 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
 */
public class IntersectionOfTwoArraysII350 {

    public static void main(String[] args) {
        int[] arr1 = {4,9,5};
        int[] arr2 = {9,4,9,8,4};
        int[] result = intersect2(arr1, arr2);
        System.out.println(Arrays.toString(result));
    }

    /**
     * HashMap
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length){
            intersect(nums2, nums1);
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int j : nums1) {
            map.put(j, map.getOrDefault(j, 0) + 1);
        }
        ArrayList<Integer> list = new ArrayList<>();
        Integer temp;
        for (int i : nums2) {
            if (!Objects.equals((temp = map.get(i)), null) && temp != 0){
                list.add(i);
                map.put(i, temp - 1);
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    /**
     * 双指针+排序（如果给定的数组已经排序好了优先选择该方法）
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int point1 = 0;
        int point2 = 0;
        int[] result = new int[Math.min(nums1.length, nums2.length)];
        int count = 0;
        while (point1 < nums1.length && point2 < nums2.length){
            if (nums1[point1] > nums2[point2]){
                point2++;
            }else if (nums1[point1] < nums2[point2]){
                point1++;
            }else {
                result[count++] = nums1[point1];
                point1++;
                point2++;
            }
        }
        return Arrays.copyOfRange(result, 0, count);
    }
}
